/*
 * @lc app=leetcode.cn id=106 lang=cpp
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 **/

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
 public:
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
  {
    TreeNode* build(postorder.begin(), postorder.end(), inorder.begin(), inorder.end());
  }

  using iter = vector<int>::iterator;  // 类型别名
  TreeNode* build(iter post_begin, iter post_end, iter in_begin,
                  iter in_end)  // post_end与in_end是哨兵
  {
    if (post_begin == post_end || in_begin == in_end) return nullptr;

    // 先找根结点（后序遍历最一个元素）
    TreeNode* root = new TreeNode(
        *(post_end - 1));  // 注意容器的end迭代器指向最后一个元素的下一个位置，而非最后一个元素！！

    // 再找左右子树（通过中序遍历，找到左右子树的分割点，求出左子树的长度）
    vector<int>::iterator in_root_pos =
        find(in_begin, in_end, root->val);  // 通过迭代器将STL中容器与算法联系起来
    int left_length = in_root_pos - in_begin;

    // 左子树(因为后序遍历是左右再node,所以左子树的范围为：post_begin～post_begin+left_length)
    root->left = build(post_begin, post_begin + left_length, in_begin, in_root_pos);

    // 右子数
    root->right = build(post_begin + left_length, post_end - 1, in_root_pos + 1, in_end);

    return root;
  }
};
// @lc code=end
